\documentclass[12pt,a4paper,italian]{article}
\usepackage[italian]{babel}
\usepackage{lastpage}
\usepackage{fancyhdr}
\usepackage{graphicx}
\usepackage[latin1]{inputenc}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{setspace}
\usepackage{hyperref}
\usepackage{multirow}
\usepackage{url}
\usepackage{chngpage}
\usepackage[left=2.5cm,right=2.5cm,top=3.8cm,bottom=3.5cm]{geometry}
\usepackage{calc}
\usepackage{wrapfig}
\usepackage{float}
%\addtolength{\oddsidemargin}{+1,3cm} %inversione destra/sinistra tradizionale Da togliere se si vogliono i bordi di grandezza uguale
%\addtolength{\evensidemargin}{-1,3cm} %inversione destra/sinistra tradizionale Da togliere se si vogliono i bordi di grandezza uguale
%\renewcommand{\familydefault}{ptm}
\onehalfspacing
%\baselineskip=24pt
%\doublespacing
%\usepackage[T1]{fontenc}
%\usepackage[scaled]{helvet}
%\renewcommand*\familydefault{\ppldefault} %% Only if the base font of the document is to be sans serif

%\pagestyle{headings}

\hypersetup{colorlinks=true, linkcolor=black, citecolor=black, urlcolor=blue}

\usepackage{amssymb}

\author{Francesco Cardin, Davide Dal Bosco}
\title{Caccia al Gigante}
\pagestyle{fancy}
\fancyhead{} %annulla head di default
%\fancyfoot{} %annulla foot di default

%testa e piede

%\lhead{\small\rightmark}
\chead{}
%\rhead{}
%\rhead{Versione 1.0}
%\lfoot{\small\leftmark}
\cfoot{\thepage}
\rfoot{}
\fancyhead[RO]{\slshape \rightmark}
\fancyhead[LE]{\slshape \leftmark}


%\renewcommand{\headrulewidth}{0.4pt}
%\renewcommand{\footrulewidth}{0.4pt}

%\fancyhead[L]{\small\rightmark}

\begin{document}



\thispagestyle{empty}
\begin{titlepage}
\changetext{}{}{}{((\paperwidth  - \textwidth) / 2) -%
             \oddsidemargin - \hoffset - 1in}{}% Per centrare la copertina
\begin{figure}
\begin{center}
\includegraphics[width=140pt]{immagini/unipd.png}
\end{center}
\end{figure}

  \begin{center}
	\begin{Huge} Universit\`a degli Studi di Padova \end{Huge}
  \end{center}
  \vspace{5pt}
  \begin{center}
	 \begin{large}Dipartimento di Matematica Pura e Applicata\end{large}
  \end{center}
   \begin{center}
	 \begin{large}Facolt\`a di Scienze Matematiche, Fisiche e Naturali\end{large}
  \end{center}
     \begin{center}
	 \begin{large}Laurea Magistrale in Informatica\end{large}
  \end{center}
 
 \vspace{17pt}
 \begin{center}
   \begin{normalsize}Relazione del progetto per il corso di Intelligenza Artificiale\end{normalsize}\\
   \begin{normalsize}redatta da Francesco Cardin 1035933 e Davide Dal Bosco 1013960\end{normalsize}
 \end{center}
 \vspace{10pt}
  \begin{center}
	 \begin{LARGE}\textbf{Caccia al Gigante}\end{LARGE}\\
	 \vspace{9pt}
	 \begin{large}\textbf{Realizzazione del gioco e del modulo di Intelligenza Artificiale}\end{large}
	 \vspace{40pt}
	 
  \end{center}
  
    \vspace{75pt}

    \begin{center}
    \begin{small}Anno Accademico 2011/2012\end{small}
    \end{center}
\end{titlepage}
%	\begin{flushright}   
%	\begin{normalsize}\end{normalsize}   
%	\end{flushright}

 \setcounter{secnumdepth}{3} % abilita la numerazione delle subsubsection
% \setcounter{tocdepth}{3}  % include le subsubsection nell'indice

\clearpage{\pagestyle{empty}\cleardoublepage}
\newpage
%\frontmatter
\tableofcontents
%\mainmatter

\newpage

\renewcommand*\thesection{\arabic{section}}

\section{Introduzione}
Questa relazione \`e il resoconto del progetto realizzato per il corso
di Intelligenza artificiale - a.a. 2012. Si \`e realizzato un gioco
con la possibilit\`a di avere come avversario il computer (l'intelligenza
artificiale). Il gioco trattato \`e \textquotedblleft{}\textbf{Caccia
al gigante}\textquotedblright{}, che essendo semplice, si presta a
un\textquoteright{}indagine di scoperta delle migliori strategie di
gioco. E' un gioco che passando di paese in paese, cambia nome, mantenendo
per\`o regole sempre simili. Nato nell\textquoteright{}Europa del Nord,
al tempo dei Vichinghi, col nome di \textquotedblleft{}La volpe e
le oche\textquotedblright{}, lo ritroviamo in Francia come \textquotedblleft{}Il
lupo e i cani\textquotedblright{}, in India diventa \textquotedblleft{}La
tigre e gli uomini\textquotedblright{} e \textquotedblleft{}Il leopardo
e le mucche\textquotedblright{}, in Cina \textquotedblleft{}Il generale
e i ribelli\textquotedblright{}. Sono giochi nei quali c\textquoteright{}\`e
sempre un \textquotedblleft{}fuggitivo\textquotedblright{} che un
gruppo \textquotedblleft{}di inseguitori\textquotedblright{} deve
riuscire a neutralizzare, accerchiandolo e impedendogli cos\`i qualsiasi
movimento.



\subsection{Regole del gioco}
Il campo \`e un reticolo, simile a quello in figura 1, di 8 posizioni. 

\begin{figure}[H]
\centering{}\includegraphics{immagini/Immagine1.png}\caption{Campo di gioco}
\end{figure}


Si gioca in due, il primo giocatore ha tre gettoni (verdi), i \textquotedblleft{}nani\textquotedblright{},
che devono essere collocati, all\textquoteright{}inizio del gioco,
nelle caselle 1, 2 e 3, il secondo giocatore ha un solo gettone (azzurro),
il \textquotedblleft{}gigante\textquotedblright{} che pu\`o essere collocato,
a scelta, in 5, 6, 7 oppure 8. 

I primi a muoversi sono i nani, che possono soltanto spostarsi su
una casella adiacente a quella in cui si trovano, ovviamente se questa
\`e libera. L\textquoteright{}intersezione delle linee 1 \textendash{}
4 e 2 \textendash{} 3 non \`e segnata da un numero e quindi non \`e possibile
collocare su tale intersezione un gettone. Ad esempio, un nano potr\`a
muoversi da 1 a 4, e indichiamo questa mossa con 1 \textendash{} 4,
ma non da 1 a 6, perch\'e dovrebbe attraversare il punto 4. Si tenga
inoltre presente che un nano non pu\`o ritornare indietro, n\'e in linea
retta, n\'e in diagonale. Ma pu\`o muoversi trasversalmente, ad esempio
da 2 a 3 oppure da 6 a 7 e gli \`e anche consentito, in questo caso,
rifare la stessa mossa al contrario. 

Si muover\`a poi il gigante, il quale pu\`o spostarsi su una casella adiacente,
secondo le stesse regole valide per i nani, ma ha in pi\`u la possibilit\`a
di fare qualsiasi mossa anche all\textquoteright{}indietro. Il gioco
prosegue con mosse alternate di nani e giganti. 

I nani per vincere devono catturare il gigante, e questo significa
chiuderlo nella casella 8, impedendogli cos\`i qualsiasi movimento.
Devono quindi riuscire ad occupare le caselle 5, 6 e 7. Se non ci
riescono hanno perso. Ma non \`e necessario che il gigante rompa l\textquoteright{}accerchiamento
per sottrarsi agli inseguitori e vincere la partita. Se si arriva
in una posizione in cui uno dei nani e il gigante continuano a ripetere
sempre la stessa mossa, per tre volte di seguito, ha vinto il gigante.
Se il gigante riesce ad attraversare la linea dei nani e arrivare
in posizione 1, ottiene la vittoria.


\section{Realizzazione}

Si descrive sinteticamente l'architettura del software allo scopo
di agevolare la comprensione del codice prodotto.

Si \`e usato un pattern MVC per facilitare la scrittura concorrente
del codice. La classe \textit{Model} contiene le strutture dati e
i metodi per accedere alle strutture e modificarle; le classi \textit{GameModeView}
e \textit{View} costituiscono l'interfaccia grafica utente, e la classe
\textit{Controller} contiene la logica dell'applicazione e gestisce
le istanze delle classi appena citate. La classe \textit{Main} istanzia
il pattern MVC, quindi da eseguire per avviare il software. Le classi
\textit{Mossa}, \textit{Personaggio} e \textit{Shot} sono classi di
utilit\`a. Infine la classe \textit{CacciaAlGiganteAI} implementa l'intelligenza
artificiale del software sviluppato e alla sua trattazione \`e dedicata
una sezione pi\`u avanti a parte.

\paragraph{Interazione con la GUI}

Nel paragrafo si descrive brevemente (ove fosse necessario) come interagire
con la GUI del gioco.

All'avvio dell'applicazione \`e presentata una finestra (vedi figura
seguente) per la scelta della modalit\`a di gioco

\begin{figure}[H]
\centering{}\includegraphics{immagini/Immagine2.png}

\caption{Finestra {}``scelta della modalit\`a'' - GameModeView.java}
\end{figure}


La modalit\`a \`e selezionabile tra le tre: 
\begin{itemize}
\item {}``Gigante vs AI'' - l'utente usa il gigante;
\item {}``Nani vs AI'' - l'utente usa i nani;
\item {}``Gigante vs Nani'' - partita tra due utenti.
\end{itemize}
Nelle modalit\`a in cui il gigante \`e usato da un utente, quest'ultimo
sceglie da che posizione partire tra 5, 6, 7 e 8; nelle modalit\`a con
avversario il computer si pu\`o scegliere che difficolt\`a affrontare
e spiegate pi\`u avanti. Cliccando {}``Gioca!'' la partita inizia.

La schermata presentata \`e la seguente

\begin{figure}[H]
\centering{}\includegraphics[scale=0.85]{immagini/Immagine3.png}

\caption{Finestra {}``Caccia al gigante'' - View.java}
\end{figure}


Essa mostra la scacchiera, aggiornata con lo svolgimento della partita,
nel pannello di sinistra; mentre a destra mostra i pannelli turni
e log. Il pannello turni mostra l'attuale turno e da' la possibilit\`a
di specificare una mossa attraverso le posizioni dello spostamento,
da eseguire col bottone {}``Muovi''; mentre log presenter\`a la storia
della partita, eventuali avvisi di mancata validazione e avvisi di
vittoria partita.

\newpage
\section{Modulo di Intelligenza Artificiale}
Il modulo di intelligenza artificiale realizzato prevede l'utilizzo dell'algoritmo MiniMax per la ricerca della mosse a cui si aggiunge il test di taglio e l'utilizzo di una funzione di valutazione.


\subsection{Algoritmo MiniMax}
L'algoritmo MiniMax permette di scegliere la mossa migliore supponendo che l'avversario giochi in modo ottimo e che di conseguenza scelga la sua mossa migliore. Il funzionamento di questa strategia consiste nel costruire l'andamento del gioco alternando le mosse dei due giocatori fino a quando si raggiungono gli stati terminali che corrispondono a stati di vittoria, sconfitta o pareggio a seconda del giocatore preso in considerazione.
Questo andamento del gioco viene rappresentato tramite un albero di ricerca in cui ogni nodo rappresenta una possibile configurazione di gioco e gli archi rappresentano le mosse possibili. Ad ogni nodo, a seconda del turno del giocatore, verranno generate tutte le possibili mosse consentite per quella configurazione di gioco. Un cammino che parte dal nodo radice (configurazione iniziale) e raggiunge uno dei nodi terminali (foglie) rappresenta una  possibile sequenza di mosse che possono essere giocate. Una volta che l'algoritmo raggiunge una foglia viene
data una valutazione della configurazione finale raggiunta tramite la funzione di utilit\`a, in relazione a quale giocatore ha conseguito una vittoria, sconfitta o pareggio.
All'interno dell'albero di ricerca, i giocatori vengono convenzionalmente chiamati MAX e MIN. Solitamente il turno iniziale viene giocato da MAX: per scegliere la mossa migliore e 
cio\`e quella che porta a stati terminali a lui pi\`u convenienti, scende l'albero fino alle foglie per ottenere il valore della funzione di utilit\`a e risale l'albero all'indietro considerando 
che anche il giocatore MIN giochi in modo ottimo. Questo si ottiene, nel caso del turno di MAX, assegnando ad ogni nodo padre il valore massimo dei valori dei figli. Viceversa, se il 
turno \`e di MIN, si assegna ad ogni padre il valore minimo dei valori dei figli. Con questa strategia, e l'assegnazione dei valori ai nodi in modo ricorsivo, \`e possibile ottenere la 
mossa migliore per ciascun giocatore ipotizzando che il proprio avversario giochi in modo ottimo.
Come \`e noto, l'algoritmo soffre del problema dell'esplosione dell'albero di ricerca, in quanto viene generato un albero di dimensioni troppo elevate e percorrerlo in tempi accettabili 
risulta impossibile.
Per questo motivo \`e stato inserito un test di taglio, in aggiunta al test terminale, descritto nel paragrafo successivo.\\
La nostra implementazione del Minimax prevede l'utilizzo di tre metodi: \textit{scelta\_mossa}, \textit{MaxMove} e \textit{MinMove}. Il personaggio gigante \`e il giocatore che massimizza (MAX) mentre il personaggio nano \`e il giocatore che minimizza (MIN). \\
Il metodo \textit{scelta\_mossa} \`e quello che sceglie la mossa migliore lanciando la strategia MiniMax, a seconda dell'intelligenza corrente che si sta utilizzando. Nel caso del gigante, il primo livello dell'algoritmo MiniMax viene gestito catturando la prima mossa possibile del gigante e chiamando il metodo MinMove per il turno dei nani. Il valore ritornato rappresenter\`a il valore massimo fino a quel punto trovato. Vengono poi valutate le altre mosse possibili del gigante (chiamando MinMove per il turno dei nani), confrontando il valore corrente con quello del valore massimo e se il valore corrente \`e superiore viene sostituito a quello massimo. Il caso dei nani \`e analogo: la differenza sta nel fatto che viene chiamato il metodo MaxMove per il turno del gigante e il valore minimo trovato viene sostituito se il il valore corrente ritornato dal metodo MaxMove \`e inferiore.\\
In questo metodo viene gestito il primo livello dell'algoritmo MiniMax, mentre le fasi ricorsive tipiche dell'algoritmo sono realizzate dai metodi MaxMove e MinMove.\\
Il metodo \textit{MaxMove} \`e il metodo ricorsivo che massimizza la valutazione del gigante. Il caso base controlla se il nodo corrente rappresenta una configurazione di gioco 
terminale oppure si \`e giunti al livello di profondit\`a prestabilito: se si \`e giunti ad una configurazione terminale vincente per il gigante viene restituito il punteggio massimo 
altrimenti se si tratta di una configurazione terminale vincente per i nani viene restituito il punteggio minimo. Nel caso in cui si \`e raggiunto il livello di profondit\`a prestabilito 
viene richiamata la funzione di valutazione per il calcolo del punteggio.\\
Il metodo prosegue poi con la generazione delle mosse e per ogni mossa viene chiamato il corrispondente metodo ricorsivo MinMove generando cosi 
l'alternanza delle mosse di gioco (turno dei nani). Al ritorno dalla ricorsione, viene confrontato il valore massimo con il valore ottenuto e se quest'ultimo \`e migliore viene sosituito al valore 
massimo. Il metodo ritorna poi il valore migliore.\\
Il metodo \textit{MinMove} \`e il metodo ricorsivo che minimizza la valutazione dei nani. Il funzionamento \`e analogo al precedente con la differenza che viene chiamato il 
metodo MaxMove (turno del gigante) e il confronto del valore attuale viene fatto col valore minimo ottenuto che poi viene restituito.\\
In tutti e tre i metodi \`e presente il controllo delle mosse ripetute che comporta la vittoria del gigante.


\newpage
\subsection{Test di taglio}
Il test di taglio permette di terminare la ricerca una volta raggiunta una certa profondit\`a fissata dell'albero di ricerca. In questo modo si evita il problema dell'esplosione dell'albero di ricerca accennato precedentemente.\\
Utilizzando il test di taglio, solitamente, non vengono raggiunte le foglie bens\`i dei nodi interni che diventeranno le nuove foglie dell'albero. In questo caso, la funzione di utilit\`a non \`e pi\`u applicabile dato che il livello in cui viene fatto il taglio contiene nodi che non dispongono di tutta l'informazione necessaria per valutare se la configurazione presa in considerazione comporti un esito finale del gioco esatto (vittoria, sconfitta o pareggio). Per questo motivo, quando l'algoritmo si trova nel livello di taglio, la valutazione della configurazione del gioco raggiunta viene fornita da una funzione di valutazione che rappresenta un valore di stima del nodo raggiunto e non pi\`u un valore esatto.
E' importante decidere quali valori di taglio utilizzare: nel nostro caso, abbiamo utilizzato tre valori di taglio: 2, 6 e 10 ply. La scelta di questi valori \`e dovuta a motivi di tempi di risposta: abbiamo valutato che un tempo ragionevole di risposta da parte del computer debba essere non superiore a 6-7 secondi. Con livelli di profondit\`a superiori il tempo di risposta risulta essere troppo elevato per l'utente.  




\subsection{Funzione di valutazione}
La funzione di valutazione viene utilizzata per stimare i nodi raggiunti nel livello di taglio al posto della funzione di utilit\`a. La nostra funzione di valutazione \`e stata realizzata su misura per l'intelligenza del gigante: ad ogni posizione del gigante, vengono analizzati i cammini a partire dalla sua casella corrente fino alla casella 1 (posizione di vittoria per il gigante). In relazione al fatto della presenza o meno dei nani in questi cammini vengono dati dei punteggi differenti come \`e spiegato nelle sezioni successive. Inoltre viene associata una componente di ripetizione riguardante la possibile ripetizione di sequenze di mosse che determina la vittoria del gigante.
La funzione di valutazione utilizzata \`e strutturata in due componenti di punteggio che concorrono per la restituzione di un valore: \textit{magic paths} e \textit{value without free paths}. Il valore
da restituire viene poi pesato per la componente di ripetizione \textit{value repetition seq}.



\subsubsection{Il metodo \textit{magic_paths}}
Questa componente di punteggio \`e quella che ha la priorit\`a maggiore rispetto a value without free paths: la funzione di valutazione controlla prima di tutto il valore restituito da magic paths e poi di conseguenza prende in considerazione l'altra componente di punteggio.
Considerando una casella della board, un magic path \`e il cammino minimo, libero e verso il basso che parte da quella casella fino all'obiettivo (casella 1). Per cammino minimo si intende un cammino con il numero minimo di passi per raggiungere l'obiettivo a partire dalla casella corrente. Per cammino libero si intende un cammino che permette di raggiungere l'obiettivo, i cui nodi non sono occupati da avversari (in questo caso da uno dei nani).
Nella figura 4 \`e mostrato un esempio di cammino minimo: il gigante si trova in 7 e i nani si trovano nelle posizioni di partenza 1,2 e 3. Dalla casella 7 un possibile cammino minimo \`e quello evidenziato in figura che passa per la casella  4 prima di raggiungere l'obiettivo. Un altro possibile cammino minimo \`e quello passante per la casella 3.
Nella figura 5 \`e mostrato un esempio di cammino libero: il gigante si trova in 8 e i nani si trovano in 3,6 e 7. Dalla casella 8 un possibile cammino libero \`e quello evidenziato in figura che passa per le caselle 5,4 e 2 prima di raggiungere l'obiettivo. In questa situazione, rispetto alla precedente, l'obiettivo non deve essere occupato da un nano.
Nella figura 6 \`e mostrato un esempio di magic path: il gigante si trova in 7 e i nani si trovano in 4,5 e 6. Dalla casella 7 l'unico magic path \`e quello evidenziato in figura che passa per 3 prima di raggiungere l'obiettivo.
Da notare che magic paths valuta solo cammini verso il basso e non permette mosse laterali.


\begin{figure}[h]
 \begin{minipage}[b]{8.5cm}
%   \centering
   \includegraphics[width=8cm]{immagini/minimo.png}
   \caption{cammino minimo}
 \end{minipage}
 \begin{minipage}[b]{8.5cm}
%  \centering
   \includegraphics[width=8cm]{immagini/libero.png}
   \caption{cammino libero}
 \end{minipage}
\end{figure}

%\vspace{100pt}

\begin{figure}[h]
\begin{center}
\includegraphics[width=8.5cm]{immagini/magic.png}
\caption{magic path}
\end{center}
\end{figure}









Questa componente, considerando le casistiche descritte precedentemente, calcola per ogni posizione nella quale si viene a trovare il gigante, il numero di magic paths presenti per quella posizione. Questo valore viene poi pesato per la distanza del magic path in modo da discriminare i cammini anche in relazione del numero di passi necessari per raggiungere l'obiettivo. Senza l'utilizzo del peso, possono verificarsi delle situazioni in cui due configurazioni di gioco, di cui una \`e pi\`u conveniente rispetto all'altra, ottengano lo stesso punteggio. Un esempio di questa situazione \`e mostrato nelle figure 7 e 8:
nella figura 7, il gigante si trova in 5 e i nani in 3,4 e 6. Con questa configurazione il numero di magic paths \`e 1 (cammino evidenziato in figura). Nella figura 8, i nani si trovano nella stessa posizione del caso precedente mentre il gigante si trova in 2. Anche in questo caso il numero di magic paths \`e 1 (cammino evidenziato in figura). In queste due situazioni, se la componente di magic paths non utilizzasse il peso, il valore restituito sarebbe identico (valore uguale a 1), dando quindi la stessa valutazione ad entrambe le configurazioni. Questo non sarebbe corretto in quanto \`e evidente che la configurazione in figura 8 \`e migliore rispetto a quella della figura 7 perch\`e in una mossa il gigante potrebbe arrivare all'obiettivo e ottenere la vittoria. Con l'inserimento del peso, la valutazione risulta essere  pi\`u corretta: nel secondo caso, il valore viene pesato per la sua distanza (distanza uguale a 1), ottenendo il valore di magic paths 1. Nel primo caso, con l'inserimento del peso (distanza uguale a 2), viene assegnato il valore di magic paths 1/2. Con questi due risultati la componente magic paths dar\`a una valutazione migliore alla situazione della figura 8. 
\\Il punteggio minimo ottenibile con questa componente \`e 1/3 (situazione nella quale il gigante \`e in 8), quindi il punteggio massimo dell'altra componente non deve superare questo limite in quanto il suo contributo ha una prioti\`a pi\`u bassa rispetto alla componente di magic paths.


\begin{figure}[h]
 \begin{minipage}[b]{8.5cm}
   \centering
   \includegraphics[width=8cm]{immagini/caso1.png}
   \caption{primo caso}
 \end{minipage}
 \ \hspace{2mm} \hspace{3mm} \
 \begin{minipage}[b]{8.5cm}
  \centering
   \includegraphics[width=8cm]{immagini/caso2.png}
   \caption{secondo caso}
 \end{minipage} 
\end{figure}


\subsubsection{Il metodo \textit{valueWithoutFreePaths}}

Il metodo \textit{valueWithoutFreePaths} compone la funzione di valutazione
per uno stato in cui il gigante non ha cammini minimi liberi dalla
sua posizione alla posizione 1 (quella di vittoria). I valori ritornati
(minori al minimo valore ritornabile in presenza di \textquotedblleft{}magic\_paths\textquotedblright{})
sono crescenti secondo la bont\`a della posizione del gigante, bont\`a
derivata da stime di preferenza anche empiriche. Ecco i valori, in
tabella:

\smallskip{}


\begin{tabular}{|c|c|p{6cm}|}
\hline 
pos. gigante & valore ritornato & motivazione\tabularnewline
\hline 
\hline 
2/3/4 & 3/12 & pos. 1 raggiungibile con una mossa\tabularnewline
\hline 
5/7 & 2/12 & pos. 1 non raggiungibile con una mossa; due cammini \textquotedblleft{}in avanti\textquotedblright{}\tabularnewline
\hline 
6 & 1/12 & pos. 1 non raggiungibile con una mossa; un cammino \textquotedblleft{}in avanti\textquotedblright{}\tabularnewline
\hline 
8 & 2/12 & pos. 1 non raggiungibile con una mossa; tre cammini \textquotedblleft{}in avanti\textquotedblright{}\tabularnewline
\hline 
\end{tabular}

\smallskip{}

\subsubsection{Il metodo \textit{valueRepetitionSeq}}

Si \`e scritto che il gigante pu\`o vincere anche per triplice ripetizione
di mossa; cio\`e, se la sua ultima mossa chiude la sequenza di shot
S0-S1-S2-S3-S0-S1-S2-S3-S0, in cui uno shot \`e una \textquotedblleft{}foto\textquotedblright{}
della scacchiera (che cattura le posizioni di nani e gigante); per
inciso: S0 e S2 sono shot conseguenti a mosse del gigante, S1 e S3
dei nani. Quindi va considerata anche questa condizione di vittoria
nella funzione di valutazione. Il metodo \textit{valueRepetitionSeq}
stima la possibilit\`a di vittoria per ripetizione di mosse, secondo
la lunghezza (numero di shot) della sequenza di ripetizione S0-S1-S2-S3-S0-S1-S2-S3-S0;
ritorna un valore reale compreso tra 0 e 1, crescente con la lunghezza
della sequenza a partire dalla prima ripetizione. Precisamente, in
tabella:

\smallskip{}


\begin{tabular}{|c|c|}
\hline 
lunghezza & valore ritornato\tabularnewline
\hline 
\hline 
1/2/3/4 & 0\tabularnewline
\hline 
5 & 0,25\tabularnewline
\hline 
6 & 0,5\tabularnewline
\hline 
7 & 0,75\tabularnewline
\hline 
8 & 1\tabularnewline
\hline 
\end{tabular}

\smallskip{}
Il valore ritornato moltiplicato per 0,5 - la vittoria per ripetizione
vale la met\`a di una vittoria per arrivo in posizione 1 - \`e sommato
alla funzione di valutazione. (La funzione di valutazione descritta
in precedenza dava valori minori o uguali a 1).


\section{Consuntivo temporale}

\begin{tabular}{|c|c|c|}
\hline 
fase/membro & Francesco Cardin & Davide Dal Bosco\tabularnewline
\hline 
\hline 
documentazione & 6 ore & 6 ore\tabularnewline
\hline 
studio del gioco & 8 ore & 12 ore\tabularnewline
\hline 
analisi requisiti & 4 ore & 4 ore\tabularnewline
\hline 
progettazione & 4 ore & 4 ore\tabularnewline
\hline 
sviluppo & 23 ore & 19 ore\tabularnewline
\hline 
\textbf{totale} & \textbf{45 ore} & \textbf{45 ore}\tabularnewline
\hline 
\end{tabular}

\end{document}
